#ifndef _INTERVAL_H_
#define _INTERVAL_H_
#include "LabelHelper.h"
typedef std::pair<int, int> IntPair;

class pair_comp 
{
public:
    bool operator() (const IntPair p1, const IntPair p2) const 
    {
	return (p1.first < p2.first) || (p1.first == p2.first && p1.second < p2.second);
    }
};

class pair_comp1
{
public:
    bool operator() (const IntPair p1, const IntPair p2) const 
    {
	return (p1.first > p2.first) || (p1.first == p2.first && p1.second > p2.second);
    }
};

typedef set<IntPair, pair_comp> PairSet;
typedef set<IntPair, pair_comp1> PairSet1;

class Interval 
{
public:
    //map< int, PairSet > interval; // store interval labels
    //IntPair interval; // tree intervals
    //map< int, PairSet > non_tree_intervals; //(tylor, non-tree edge intervals, for tree interval use interval
    map< int, PairSet > intervals; // all intervals, map is already sorted by key
    // auxiliary data
    std::set<Vertex> roots; // root of each spanning tree
    // specific methods
    void findOptTree();
public:
    // graph
    Graph& g;
    LabelHelper helper;
    // constructor
    Interval( Graph& graph );
    // assign labels, return number of intervals;
    int createLabels(bool display);
    int createNonTreeLabels(bool display);
    int createNonTreeLabels1(bool display);//assign Non tree intervals to special nodes (I, O nodes, i.e. exlcude normal nodes)     
    int createNonTreeLabels2(bool display);//assign Non tree intervals to all nodes, but do not propagate non-tree intervals via tree edges
    int createTreeLabels(bool display);
    bool has_non_tree_edge(Vertex v);
    // display
    void displayLabels();	
    // query
    bool reachable( Vertex u, Vertex v );
    bool reachable( int u, int v);
    void testReach( int );
};

#endif //_INTERVAL_H_
